/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */



// class Solution {
// public:
//     template <typename T>
//     void merge(T& nums1, int m, T& nums2, int n) {
//         int len = nums1.size();
//         while(len--)
//         if(!n || (m && nums1[m - 1] >= nums2[n - 1])) nums1[len] = nums1[--m];
//         else nums1[len] = nums2[--n];

//     }
// };

class Solution {
public:
    // template <typename T>
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int len1 = nums1.size(), len2 = nums2.size();
        for (int i = 0; i<len2; i++){
            nums1[i + m] = nums2[i];
        }
        for (int i = 1; i < nums1.size(); i++){
            int preIndex = i-1;
            int choose = nums1[i];
            while (preIndex>=0 && nums1[preIndex] > choose)
            {
                nums1[preIndex+1] = nums1[preIndex];
                preIndex--;
            }
            nums1[preIndex+1] = choose;
        }

    }
};



int main(int argc, char** argv){
    vector<int> nums1 = {1,2,3,0,0,0};
    vector<int> nums2 = {2,5,6};
    Solution solu = Solution();
    solu.merge(nums1,3,nums2,3);
    for (int i = 0; i <6;i++){
        printf("%d ", nums1[i]);
    }
    printf("\r\n");
    return 0;
}